{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximize the Profit as the Salesman"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximizeTheProfit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #销售利润最大化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code> 表示数轴上的房屋数量，编号从 <code>0</code> 到 <code>n - 1</code> 。</p>\n",
    "\n",
    "<p>另给你一个二维整数数组 <code>offers</code> ，其中 <code>offers[i] = [start<sub>i</sub>, end<sub>i</sub>, gold<sub>i</sub>]</code> 表示第 <code>i</code> 个买家想要以 <code>gold<sub>i</sub></code> 枚金币的价格购买从 <code>start<sub>i</sub></code> 到 <code>end<sub>i</sub></code> 的所有房屋。</p>\n",
    "\n",
    "<p>作为一名销售，你需要有策略地选择并销售房屋使自己的收入最大化。</p>\n",
    "\n",
    "<p>返回你可以赚取的金币的最大数目。</p>\n",
    "\n",
    "<p><strong>注意</strong> 同一所房屋不能卖给不同的买家，并且允许保留一些房屋不进行出售。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, offers = [[0,0,1],[0,2,2],[1,3,2]]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "有 5 所房屋，编号从 0 到 4 ，共有 3 个购买要约。\n",
    "将位于 [0,0] 范围内的房屋以 1 金币的价格出售给第 1 位买家，并将位于 [1,3] 范围内的房屋以 2 金币的价格出售给第 3 位买家。\n",
    "可以证明我们最多只能获得 3 枚金币。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, offers = [[0,0,1],[0,2,10],[1,3,2]]\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>有 5 所房屋，编号从 0 到 4 ，共有 3 个购买要约。\n",
    "将位于 [0,2] 范围内的房屋以 10 金币的价格出售给第 2 位买家。\n",
    "可以证明我们最多只能获得 10 枚金币。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= offers.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>offers[i].length == 3</code></li>\n",
    "\t<li><code>0 &lt;= start<sub>i</sub> &lt;= end<sub>i</sub> &lt;= n - 1</code></li>\n",
    "\t<li><code>1 &lt;= gold<sub>i</sub> &lt;= 10<sup>3</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximize-the-profit-as-the-salesman](https://leetcode.cn/problems/maximize-the-profit-as-the-salesman/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximize-the-profit-as-the-salesman](https://leetcode.cn/problems/maximize-the-profit-as-the-salesman/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[0,0,1],[0,2,2],[1,3,2]]', '5\\n[[0,0,1],[0,2,10],[1,3,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        offers.sort()\n",
    "        # f[i] 表示用第i个，前i个最大gold\n",
    "        # f[i] = max(f[j] + gold), 保证 end[j] < i\n",
    "        f = [0] * (n+1)\n",
    "        tot = 0\n",
    "        last_start = 0\n",
    "        for start, end, gold in offers:\n",
    "            tot = max(tot, max(f[last_start:start+1]))\n",
    "            f[end+1] = max(f[end+1], tot + gold)\n",
    "            last_start = start\n",
    "        # print(f)\n",
    "        return max(f)\n",
    "            \n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        groups = [[] for _ in range(n)]\n",
    "        for start, end, gold in offers:\n",
    "            groups[end].append((start, gold))\n",
    "        f = [0] * (n + 1)\n",
    "        for end, g in enumerate(groups):\n",
    "            f[end + 1] = f[end]\n",
    "            for start, gold in g:\n",
    "                f[end + 1] = max(f[end + 1], f[start] + gold)\n",
    "        return f[n]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        groups = [[] for _ in range(n)]\n",
    "        for start, end, gold in offers:\n",
    "            groups[end].append((start, gold))\n",
    "        f = [0] * (n + 1)\n",
    "        for end, g in enumerate(groups):\n",
    "            f[end + 1] = f[end]\n",
    "            for start, gold in g:\n",
    "                f[end + 1] = max(f[end + 1], f[start] + gold)\n",
    "        return f[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        offer_dict={}\n",
    "        for x in offers:\n",
    "            if offer_dict.get((x[0], x[1])):\n",
    "                offer_dict[x[0], x[1]] = max(offer_dict[x[0], x[1]], x[2])\n",
    "            else:\n",
    "                offer_dict[x[0], x[1]] = x[2]\n",
    "\n",
    "        # print(offer_dict)\n",
    "        sorted_offers = []\n",
    "        for key, value in offer_dict.items():\n",
    "            sorted_offers.append([key[0],key[1],value])\n",
    "\n",
    "        sorted_offers = sorted(sorted_offers, key=lambda x:x[1])\n",
    "        # print(sorted_offers)\n",
    "        m = len(sorted_offers)\n",
    "\n",
    "        dp = [-1] * (n+1)\n",
    "        dp[0] = 0\n",
    "\n",
    "        for j in range(m):\n",
    "            if dp[sorted_offers[j][1]]==-1:\n",
    "                x=1\n",
    "                while(dp[sorted_offers[j][1]-x]==-1):\n",
    "                    x+=1\n",
    "                dp[sorted_offers[j][1]] = dp[sorted_offers[j][1]-x]\n",
    "            if dp[sorted_offers[j][0]]==-1:\n",
    "                x=1\n",
    "                while(dp[sorted_offers[j][0]-x]==-1):\n",
    "                    x+=1\n",
    "                dp[sorted_offers[j][0]] = dp[sorted_offers[j][0]-x]\n",
    "            \n",
    "            dp[sorted_offers[j][1]+1] = max(dp[sorted_offers[j][1]+1], dp[sorted_offers[j][1]], dp[sorted_offers[j][0]]+sorted_offers[j][2])\n",
    "\n",
    "        \n",
    "        return max(dp)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    按照下面的朴素定义进行优化\n",
    "    为啥要记录当前第i个房子是卖了还是没卖呢？直接转换也可以，就一维了\n",
    "    '''\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        m = len(offers)\n",
    "        dp = [0] * (n + 1)\n",
    "\n",
    "        ends = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            ends[offers[i][1]].append(i)\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[i - 1]\n",
    "            for j in ends[i - 1]:\n",
    "                dp[i] = max(dp[i], dp[offers[j][0]] + offers[j][2])\n",
    "        \n",
    "        return dp[-1]\n",
    "\n",
    "    '''\n",
    "    朴素定义\n",
    "    dp[i][0]表示前i个房子，且第i个房子没有被卖掉的最大收入\n",
    "    dp[i][1]表示前i个房子，且第i个房子被卖掉了的最大收入\n",
    "    遍历每个房子，每个房子都有被卖和不卖两种可能，没有卖，那总收入就是前i - 1个房子，此时前\n",
    "    i - 1个房子卖与不卖都要看，取最大的那个；卖了，那就要找到offers中所有以i房子结尾的报价，\n",
    "    递推出前i - j个房子的最大收入，再加上当前以i房子结束的区间卖出的报价\n",
    "    '''\n",
    "    # def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "    #     m = len(offers)\n",
    "    #     dp = [[float('-inf')] * 2 for _ in range(n + 1)]\n",
    "    #     dp[0][0] = 0\n",
    "        \n",
    "    #     ends = defaultdict(list)\n",
    "    #     for i in range(m):\n",
    "    #         ends[offers[i][1]].append(i)\n",
    "\n",
    "    #     for i in range(1, n + 1):\n",
    "    #         dp[i][0] = max(dp[i - 1][1], dp[i - 1][0])\n",
    "    #         for j in ends[i - 1]:\n",
    "    #             dp[i][1] = max(dp[i][1], dp[offers[j][0]][0] + offers[j][2], dp[offers[j][0]][1] + offers[j][2])\n",
    "\n",
    "    #     return max(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        map=defaultdict(list)\n",
    "        for start,end,gold in offers:\n",
    "            map[end].append([start,gold])\n",
    "        # print(map)\n",
    "        dp=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            dp[i]=dp[i-1]\n",
    "            for start,gold in map[i-1]:\n",
    "                dp[i]=max(dp[i],dp[start]+gold)\n",
    "        # print(dp)\n",
    "        return dp[n]\n",
    "\n",
    "           \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        e2s = defaultdict(dict)\n",
    "        for start, end, gold in offers:\n",
    "            if end not in e2s:\n",
    "                e2s[end][start] = gold\n",
    "            else:\n",
    "                if start not in e2s[end]:\n",
    "                    e2s[end][start] = gold\n",
    "                else:\n",
    "                    e2s[end][start] = max(gold, e2s[end][start])\n",
    "\n",
    "        dp = [0]*n\n",
    "        if 0 in e2s:\n",
    "            dp[0] = e2s[0][0]\n",
    "        else:\n",
    "            dp[0] = 0\n",
    "        for i in range(1, n):\n",
    "            dp[i] = dp[i-1]\n",
    "            for start, gold in e2s[i].items():\n",
    "                dp[i] = max(dp[i], dp[start-1]+gold if start!=0 else gold)\n",
    "        # print(e2s)\n",
    "        # print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        dp = [0] * (n+1)\n",
    "        endDict = defaultdict(list)\n",
    "        for s, e, v in offers:\n",
    "            endDict[e+1].append((s+1, v))\n",
    "        for e in range(1, n+1):\n",
    "            dp[e] = dp[e-1]\n",
    "            for s, v in endDict[e]:\n",
    "                dp[e] = max(dp[e], dp[s-1]+v)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        m = len(offers)\n",
    "        dp = [[float('-inf')] * 2 for _ in range(n + 1)]\n",
    "        dp[0][0] = 0\n",
    "        \n",
    "        ends = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            ends[offers[i][1]].append(i)\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i][0] = max(dp[i - 1][1], dp[i - 1][0])\n",
    "            for j in ends[i - 1]:\n",
    "                k = i - offers[j][1] + offers[j][0] - 1\n",
    "                dp[i][1] = max(dp[i][1], dp[k][0] + offers[j][2], dp[k][1] + offers[j][2])\n",
    "\n",
    "        return max(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        \n",
    "        offers.sort()\n",
    "        \n",
    "        jump = [[(idx+1, 0)] for idx in range(n)]\n",
    "        \n",
    "        for start, end, gold in offers:\n",
    "            jump[start].append((end+1, gold))\n",
    "            \n",
    "        for start, arr in enumerate(jump):\n",
    "            for end, gold in arr:\n",
    "                dp[end] = max(dp[end], dp[start] + gold)\n",
    "        \n",
    "        return dp[-1]\n",
    "    \n",
    "s = Solution()\n",
    "assert s.maximizeTheProfit(n = 5, offers = [[0,0,1],[0,2,2],[1,3,2]]) == 3\n",
    "assert s.maximizeTheProfit(n = 5, offers = [[0,0,1],[0,2,10],[1,3,2]]) == 10\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        # offers.sort(key=lambda x: (x[0], x[1]))\n",
    "        # f = [[0] * (n + 1)]\n",
    "        # for s, e, g in offers:\n",
    "        #     s += 1\n",
    "        #     e += 1\n",
    "        #     f[e] = f[s-1] + g \n",
    "        # return f[n]\n",
    "\n",
    "        # d = defaultdict(list)\n",
    "        # for offer in offers:\n",
    "        #     d[offer[1]].append(offer)\n",
    "        # # f[i] 表示一个i结尾的最大值\n",
    "        # # f[i] = max(g + f[s])\n",
    "        # f = [0] * (n + 1)\n",
    "        # for i in range(n):\n",
    "        #     if len(d[i]) == 0:\n",
    "        #         f[i+1] = f[i]\n",
    "        #     for s, e, g in d[i]:\n",
    "        #         f[i+1] = max(f[i+1], f[s] + g, f[i])\n",
    "        # return f[n]\n",
    "\n",
    "\n",
    "        d = defaultdict(list)\n",
    "        for st, end, gold in offers:\n",
    "            d[end].append((st, gold))\n",
    "        f = [0] * (n + 1) # 以i结尾，卖或者不卖的最大值\n",
    "        # 如果不卖，就是f[i] = f[i-1]，当然如果i处没有房子，只能不卖\n",
    "        # 如果卖，就是所有以i结尾的区域，找出最大值\n",
    "        for i in range(n):  # 此处是i的含义不变，但是f[i]的含义变化\n",
    "            f[i+1] = f[i]\n",
    "            for st, gold in d[i]:\n",
    "                f[i+1] = max(f[i+1], f[st] + gold)\n",
    "        return f[n]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        groups = [[] for _ in range(n)]\n",
    "        for st, end, gold in offers:\n",
    "            groups[end].append((st, gold))\n",
    "        \n",
    "        f = [0] * (n+1)\n",
    "        for end, g in enumerate(groups):\n",
    "            f[end+1] = f[end]\n",
    "            for st, gold in g:\n",
    "                f[end+1] = max(f[end+1], f[st] + gold)\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        e2i = defaultdict(list)\n",
    "        for offer in offers:\n",
    "            l, r, c = offer\n",
    "            e2i[r].append((l, c))\n",
    "        dp = [0 for i in range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            if i > 0:\n",
    "                dp[i] = dp[i-1]\n",
    "            for v in e2i[i]:\n",
    "                l, c = v\n",
    "                last = 0\n",
    "                if l > 0:\n",
    "                    last = dp[l-1]\n",
    "                dp[i] = max(dp[i], last + c)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        dp = [0] * (n + 1)\n",
    "        records = collections.defaultdict(lambda:[])\n",
    "        for s, e, g in offers:\n",
    "            records[e + 1].append((s + 1, g))\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[i - 1]\n",
    "            for j, g in records[i]:\n",
    "                dp[i] = max(dp[i], dp[j - 1] + g)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        offers.sort()\n",
    "        start_l = [i[0] for i in offers]\n",
    "        quick_s = dict()\n",
    "        for i, v in enumerate(start_l):\n",
    "            if v not in quick_s:\n",
    "                quick_s[v] = i\n",
    "        @cache\n",
    "        def findi(start):\n",
    "            if start >= n:\n",
    "                return 0\n",
    "            if start not in quick_s:\n",
    "                return findi(start+1)\n",
    "            idx = quick_s[start]\n",
    "            res = 0\n",
    "            while idx < len(start_l) and start_l[idx] == start:\n",
    "                res = max(res, offers[idx][2] + findi(offers[idx][1] + 1))\n",
    "                idx += 1\n",
    "            return max(res, findi(start+1))\n",
    "        return findi(0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for o in offers:\n",
    "            d[o[0]].append(o)\n",
    "          \n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            if i not in d:\n",
    "                return f(i + 1)\n",
    "            return max(max(g + f(e + 1) for s, e, g in d.pop(i)), f(i + 1))\n",
    "          \n",
    "        return f(0)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        dp = [0 for i in range(n)]\n",
    "        apof = [[i,i,0] for i in range(n)]\n",
    "        offers += apof\n",
    "        offers.sort(key = lambda x:x[1])\n",
    "        for s,e,g in offers:\n",
    "            if s != 0:\n",
    "                dp[e] = max(dp[e], dp[s-1] + g)\n",
    "            else:\n",
    "                dp[e] = max(dp[e], g)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        # 动态规划\n",
    "        # f[i]代表以i结尾的房子的最大值\n",
    "        dic = defaultdict(list)\n",
    "        for offer in offers:\n",
    "            a, b, c = offer\n",
    "            dic[b+1].append([a+1, b+1, c])\n",
    "        # print(dic)\n",
    "        f = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            arr = dic[i]\n",
    "            # print(arr)\n",
    "            for t in arr:\n",
    "                f[i] = max(f[i], f[t[0]-1] + t[2])\n",
    "            f[i] = max(f[i], f[i-1])\n",
    "        # print(f)\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:#题解方法，线性dp，根据offer结尾时间分类，按卖或不卖讨论\n",
    "        dc=defaultdict(Counter)#(int)记录相同结尾、相同开头的最大金额\n",
    "        for i in offers:\n",
    "            dc[i[1]][i[0]]=max(i[2],dc[i[1]][i[0]])\n",
    "        upb=max(i[1] for i in offers)#n+2#\n",
    "        dp=[0]*(upb+2)#存到右节点+1的位置\n",
    "        for i in range(1,len(dp)):\n",
    "            dp[i]=dp[i-1]\n",
    "            for j in dc[i-1]:\n",
    "                dp[i]=max(dp[i],dp[j]+dc[i-1][j])\n",
    "        # print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        # nlogn 超时（改成迭代应该可以过）\n",
    "        # offers.sort()\n",
    "        # @cache\n",
    "        # def dp(pos):\n",
    "        #     if pos == len(offers): return 0\n",
    "        #     # 选择\n",
    "        #     nxt = pos + 1\n",
    "        #     while nxt < len(offers) and offers[nxt][0] <= offers[pos][1]:\n",
    "        #         nxt += 1\n",
    "        #     ans = offers[pos][2] + dp(nxt)\n",
    "        #     # 不选择\n",
    "        #     ans = max(ans, dp(pos + 1))\n",
    "        #     return ans\n",
    "        \n",
    "        # return dp(0)\n",
    "        # 不对 offer dp，对 n dp\n",
    "        # @cache\n",
    "        # def dp(pos):\n",
    "        #     if pos == n: return 0\n",
    "        #     ans = 0\n",
    "        #     for offer in offers:\n",
    "        #         if offer[0] == pos:\n",
    "        #             # 选择\n",
    "        #             ans = max(ans, offer[2] + dp(offer[1] + 1))\n",
    "        #     # 不选择\n",
    "        #     ans = max(ans, dp(pos + 1))\n",
    "        #     return ans\n",
    "        # return dp(0)\n",
    "        # 预处理，优化一下状态转移\n",
    "        # m[x] 表示开始时间等于 x 的 offer\n",
    "        m = collections.defaultdict(list)\n",
    "        for offer in offers:\n",
    "            m[offer[0]].append(offer)\n",
    "        @cache\n",
    "        def dp(pos):\n",
    "            if pos == n: return 0\n",
    "            ans = 0\n",
    "            for offer in m[pos]:\n",
    "                ans = max(ans, offer[2] + dp(offer[1] + 1))\n",
    "            ans = max(ans, dp(pos + 1))\n",
    "            return ans\n",
    "        return dp(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "use DP \n",
    "\n",
    "f[x]:  maximum profit for lands from [0. x]\n",
    "\n",
    "\n",
    "it has to be end here\n",
    "f[x] = max(f[start_i-1] + p[i], f[x-1])\n",
    "\n",
    "\n",
    "pre-process\n",
    "\n",
    "map from any land to its entry\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "\n",
    "        house_to_buyers = defaultdict(list)\n",
    "        for buyer, offer in enumerate(offers):\n",
    "            house_to_buyers[offer[1]].append(buyer)\n",
    "\n",
    "        @cache\n",
    "        def dfs(x: int) -> int:\n",
    "            if x < 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for buyer in house_to_buyers[x]:\n",
    "                offer = offers[buyer]\n",
    "                res = max(res, dfs(offer[0] - 1) + offer[2])\n",
    "            if x > 0:\n",
    "                res = max(res, dfs(x - 1))\n",
    "            return res\n",
    "        \n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        mp = defaultdict(list)\n",
    "        for x, y, z in offers:\n",
    "            mp[x].append([y, z])\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            return max([dfs(y + 1) + z for y, z in mp[i]] + [dfs(i + 1)]) if i != n else 0\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        dp = [0 for _ in range(n)]\n",
    "        m = len(offers)\n",
    "        e = defaultdict(set)\n",
    "        for i in range(m):\n",
    "            lv,rv,v = offers[i]\n",
    "            e[rv].add((lv,v))\n",
    "        offers.sort(key = lambda x:(x[1],-x[2]))\n",
    "        dp[offers[0][1]] = offers[0][2]\n",
    "        for i in range(1,n):\n",
    "            dp[i] = max(dp[i],dp[i - 1])\n",
    "            for lst,v in e[i]:\n",
    "                if lst - 1 >= 0:\n",
    "                    dp[i] = max(dp[i],dp[lst - 1] + v)\n",
    "                else:\n",
    "                    dp[i] = max(dp[i],v)\n",
    "        return dp[-1]\n",
    "        \n",
    "            \n",
    "         \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        a = [0 for _ in range(n)]\n",
    "        idx_offers = {}\n",
    "        for i in range(n):\n",
    "            idx_offers[i] = [[i-1,0]]\n",
    "        \n",
    "        for offer in offers:\n",
    "            l,r,g = offer\n",
    "            idx_offers[r].append([l-1,g])\n",
    "        \n",
    "        for i in range(n):\n",
    "            for offer in idx_offers[i]:\n",
    "                if offer[0] == -1:\n",
    "                    prev = 0\n",
    "                else:\n",
    "                    prev = a[offer[0]]\n",
    "                \n",
    "                if prev + offer[1] > a[i]:\n",
    "                    a[i] = prev + offer[1]\n",
    "        return a[n-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:  # 线段树内每一个节点，类似二叉树表述\n",
    "    def __init__(self, l, r):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.l = l\n",
    "        self.r = r\n",
    "        self.mid = (l + r) >> 1\n",
    "        self.v = 0\n",
    "        self.add = 0\n",
    "\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self):\n",
    "        self.root = Node(1, int(1e5)+1)  # 离散化之前最大的数值范围为[1, 10^5]\n",
    "\n",
    "    def modify(self, l, r, v, node=None):  # 将【l,r】区间数值修改为 v\n",
    "        if l > r:\n",
    "            return\n",
    "        if node is None:\n",
    "            node = self.root\n",
    "        if node.l >= l and node.r <= r:\n",
    "            node.v = v\n",
    "            node.add = v\n",
    "            return\n",
    "        self.pushdown(node)\n",
    "        if l <= node.mid:\n",
    "            self.modify(l, r, v, node.left)\n",
    "        if r > node.mid:\n",
    "            self.modify(l, r, v, node.right)\n",
    "        self.pushup(node)\n",
    "\n",
    "    def query(self, l, r, node=None):  # 查询区间[l,r]内的最大值，如果为其他函数需要修改\n",
    "        if l > r:\n",
    "            return 0\n",
    "        if node is None:\n",
    "            node = self.root\n",
    "        if node.l >= l and node.r <= r:\n",
    "            return node.v\n",
    "        self.pushdown(node)\n",
    "        v = 0\n",
    "        if l <= node.mid:\n",
    "            v = max(v, self.query(l, r, node.left))  # 查询区间[l,r]内的最大值，如果为其他函数需要修改\n",
    "        if r > node.mid:\n",
    "            v = max(v, self.query(l, r, node.right))  # 查询区间[l,r]内的最大值，如果为其他函数需要修改\n",
    "        return v\n",
    "\n",
    "    def pushup(self, node):  # 标志是否需要向上刷新，如果不是最大值，需要修改\n",
    "        node.v = max(node.left.v, node.right.v)\n",
    "\n",
    "    def pushdown(self, node):  # 标志是否需要向下刷新，懒惰更新\n",
    "        if node.left is None:\n",
    "            node.left = Node(node.l, node.mid)\n",
    "        if node.right is None:\n",
    "            node.right = Node(node.mid + 1, node.r)\n",
    "        if node.add:\n",
    "            node.left.v = node.add\n",
    "            node.right.v = node.add\n",
    "            node.left.add = node.add\n",
    "            node.right.add = node.add\n",
    "            node.add = 0\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: [[int]]) -> int:\n",
    "        #1.排序 根据【结束日期，效率】排序\n",
    "        #2. dp[i] 表示处理到 第i个房间后的最大效益， 前面的0--i 个房间已经被处理完毕了，\n",
    "        #3. 每次处理列表中的数字的时候， 是[s,e]\n",
    "        #4. 线段树， 区间[x,y]为该区间内最大值， 然后每次加入一颗新的树\n",
    "\n",
    "        tree = SegmentTree()\n",
    "        offers.sort(key=lambda x: (x[1], x[0],x[2]))\n",
    "        for i in range(len(offers)):\n",
    "            left  = offers[i][0]+1\n",
    "            rigth = offers[i][1]+1\n",
    "\n",
    "            maxleft=tree.query(1,left-1)\n",
    "            cur=maxleft+offers[i][2]\n",
    "            maxright = tree.query(1,rigth)\n",
    "            if cur>maxright:\n",
    "                tree.modify(rigth,rigth,cur)\n",
    "\n",
    "        return tree.query(1,int(1e5)+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        # a left_bound, b right_bound, c value, d left_child, e right_child\n",
    "        a,b,c,d,e = \"l\",\"r\",\"val\",\"left\",\"right\"\n",
    "        debug = 0\n",
    "        def _build(l,r):\n",
    "            now = {}\n",
    "            now[a] = l\n",
    "            now[b] = r\n",
    "            now[c] = 0\n",
    "            if l != r:\n",
    "                m = l+(r-l)//2\n",
    "                now[d] = _build(l,m)\n",
    "                now[e] = _build(m+1,r)\n",
    "            return now\n",
    "        root = _build(0,n-1)\n",
    "        def _update(now,idx,v):\n",
    "            if debug:\n",
    "                # print(idx,v,now)\n",
    "                pass\n",
    "            l,r = now[a],now[b]\n",
    "            if l == idx and r == idx:\n",
    "                now[c] = max(now[c],v)\n",
    "                return now[c]\n",
    "            m = l+(r-l)//2\n",
    "            if idx <=m:\n",
    "                now[c] = max(_update(now[d],idx,v),now[c])\n",
    "            else:\n",
    "                now[c] = max(now[c],_update(now[e],idx,v))\n",
    "            return now[c]\n",
    "        def _get(now,x,y):\n",
    "            l,r = now[a],now[b]\n",
    "            if x<=l and r<=y:\n",
    "                return now[c]\n",
    "            if r<x or y<l:\n",
    "                return -1\n",
    "            m = l+(r-l)//2\n",
    "            return max(_get(now[d],x,y),_get(now[e],x,y))\n",
    "        for l,r,p in sorted(offers):\n",
    "            x = 0\n",
    "            if l:\n",
    "                x = _get(root,0,l-1)\n",
    "            _update(root,r,p+x)\n",
    "        if debug:\n",
    "            out = []\n",
    "            def _print(now):\n",
    "                out.append([now[a],now[b],now[c]])\n",
    "                if d in now:\n",
    "                    _print(now[d])\n",
    "                    _print(now[e])\n",
    "            _print(root)\n",
    "            print(out)\n",
    "        return _get(root,0,n-1)\n",
    "'''\n",
    "5\n",
    "[[0,0,1],[0,2,2],[1,3,2]]\n",
    "5\n",
    "[[0,0,1],[0,2,10],[1,3,2]]\n",
    "4\n",
    "[[0,0,5],[3,3,1],[1,2,5],[0,0,7]]\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        offers.sort()\n",
    "        ln=len(offers)\n",
    "        @lru_cache(None)\n",
    "        def f(p):\n",
    "            if p==ln:\n",
    "                return 0\n",
    "            r=f(p+1)\n",
    "            p1=bisect_left(offers,[offers[p][1]+1,0,0])\n",
    "            r=max(r,offers[p][2]+f(p1))\n",
    "            # print(p,r)\n",
    "            return r\n",
    "        return f(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, a: List[List[int]]) -> int:\n",
    "        m=len(a)\n",
    "        a.sort()\n",
    "        @cache\n",
    "        def dfs(p):\n",
    "            if p>=m:\n",
    "                return 0\n",
    "            i=bisect_right(a,[a[p][1],inf,inf])\n",
    "            return max(dfs(p+1),dfs(i)+a[p][2])\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        l = defaultdict(list)\n",
    "        for o in offers:\n",
    "            l[o[1]].append(o)\n",
    "\n",
    "        @cache\n",
    "        def zz(i):\n",
    "            if i == -1:\n",
    "                return 0\n",
    "\n",
    "            off = l.get(i, [])\n",
    "            maxa = zz(i - 1)\n",
    "            for o in off:\n",
    "                maxa = max(maxa, zz(o[0] - 1) + o[2])\n",
    "\n",
    "            return maxa\n",
    "\n",
    "        ans = zz(n - 2)\n",
    "        for o in l.get(n - 1, []):\n",
    "            ans = max(ans, zz(o[0] - 1) + o[2])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        # dp = [0] * n\n",
    "        # offers.sort(key=lambda x: x[1])\n",
    "        # pre_max = i = 0\n",
    "        # for l, r, g in offers:\n",
    "        #     while i < r:\n",
    "        #         pre_max = max(dp[i], pre_max)\n",
    "        #         dp[i] = pre_max\n",
    "        #         i += 1\n",
    "        #     dp[r] = max(dp[r], (dp[l-1] if l > 0 else 0)+g)\n",
    "        # return max(dp)\n",
    "\n",
    "        # ------------------------------\n",
    "        # dp = [0] * (n+1)\n",
    "        # same_end = [[] for _ in range(n)]\n",
    "        # for s, e, g in offers:\n",
    "        #     same_end[e].append((s, g))\n",
    "        # for e, others in enumerate(same_end):\n",
    "        #     dp[e+1] = dp[e]\n",
    "        #     for s, g in others:\n",
    "        #         dp[e+1] = max(dp[e+1], dp[s]+g)\n",
    "        # return dp[-1]\n",
    "\n",
    "        # -------------------------------\n",
    "        @cache \n",
    "        def sell(i):\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            return max(sell(i-1), max([sell(start-1)+gold for start, gold in same_end[i]], default=0))\n",
    "        \n",
    "        same_end = [[] for _ in range(n)]\n",
    "        for s, e, g in offers:\n",
    "            same_end[e].append((s, g))\n",
    "        return sell(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:\n",
    "        group = [[] for _ in range(n)]\n",
    "\n",
    "        for s,e,g in offers:\n",
    "            group[e].append((s,g))\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dfs(i:int)->int:\n",
    "            if i == -1:\n",
    "                return 0\n",
    "            ans =dfs(i-1)  \n",
    "            for start,gold in group[i]:\n",
    "                ans = max(dfs(start-1)+gold,ans)\n",
    "            return ans\n",
    "            \n",
    "        return dfs(n-1)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
